package sort

func CountingSort(a []int, n int) {
	if n <= 1 {
		return
	}
	var max = getMax(a)

	c := make([]int, max+1)
	// 统计每个值得元素个数
	for i := range a {
		c[a[i]]++
	}
	// 从左到右（从小到大）累加
	for i := 1; i <= max; i++ {
		c[i] += c[i-1]
	}

	// 原始数据桶
	r := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		index := c[a[i]] - 1
		r[index] = a[i]
		c[a[i]]--
	}

	copy(a, r)
}
